package class71To80;

import java.io.*;

public class TSP {

    public static int MAX_N = 19;

    public static int[][] dp = new int[1 << MAX_N][MAX_N];

    public static int[] start = new int[MAX_N];

    public static int[] back = new int[MAX_N];

    public static int[][] graph = new int[MAX_N][MAX_N];

    public static int n;


    public static void build() {
        for (int s = 0; s < (1 << n); s++) {
            for (int i = 0; i < n; i++) {
                dp[s][i] = -1;
            }
        }
    }


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(System.out);
        while (in.nextToken() != in.TT_EOF) {
            n = (int) in.nval-1;
            build();
            in.nextToken();
            for (int i = 0; i < n; i++) {
                in.nextToken();
                start[i] = (int) in.nval;
            }
            for (int i = 0; i < n; i++) {
                in.nextToken();
                back[i] = (int) in.nval;
                for (int j = 0; j < n; j++) {
                    in.nextToken();
                    graph[i][j] = (int) in.nval;
                }
            }
            out.println(solve());
        }
        out.flush();
        out.close();
        br.close();
    }

    public static int solve() {
        int ans = Integer.MAX_VALUE;
        // 起始村无编号
        for (int i = 0; i < n; i++) {
            // 起始村 -> i号村  +  i号村出发所有村子都走最终回到起始村
            ans = Math.min(ans, start[i] + f2(1 << i, i));
        }
        return ans;
    }

    public static int f(int status, int in) {
        if (status == (1 << n) - 1) {
            return graph[in][0];
        }
        if (dp[status][in] != -1) {
            return dp[status][in];
        }
        int ans = Integer.MAX_VALUE;
        for (int j = 0; j < n; j++) {
            // 0...n-1这些村，都看看是不是下一个落脚点
            if ((status & (1 << j)) == 0) {
                ans = Math.min(ans, graph[in][j] + f(status | (1 << j), j));
            }
        }
        dp[status][in] = ans;
        return ans;
    }

    public static int f2(int s, int i) {
        if (s == (1 << n) - 1) {
            return back[i];
        }
        if (dp[s][i] != -1) {
            return dp[s][i];
        }
        int ans = Integer.MAX_VALUE;
        for (int j = 0; j < n; j++) {
            if ((s & (1 << j)) == 0) {
                ans = Math.min(ans, graph[i][j] + f2(s | (1 << j), j));
            }
        }
        dp[s][i] = ans;
        return ans;
    }

}
